#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""
https://www.lintcode.com/problem/diameter-of-binary-tree/description

Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    param root: a root of binary tree
    return: return a integer
    """
    def diameterOfBinaryTree(self, root):
        return self.diameter_rec(root)[0]

    def diameter_rec(self, node):
        max_dis, max_height = 0, 0

        left_max_dis, left_max_height = -1, -1
        right_max_dis, right_max_height = -1, -1

        if node.left:
            left_max_dis, left_max_height = self.diameter_rec(node.left)

        if node.right:
            right_max_dis, right_max_height = self.diameter_rec(node.right)

        return max(left_max_height + right_max_height + 2, left_max_dis, right_max_dis), max(left_max_height, right_max_height)+1


def main():
    print("start main")

if __name__ == "__main__":
    main()
